The invention relates to methods and apparatus for designing packet-based networks and, more particularly, for designing IP (Internet Protocol) networks with performance guarantees.
Traditional IP networks are built with very limited capacity planning and design optimization. These networks can only provide a best-effort service without performance guarantees. However, customer expectations can only be met if IP networks are designed to provide predictable performance. In particular, network service providers have to support bandwidth guarantees for their virtual private network (VPN) customers.
In addition, included in any network design considerations, is the fact that there are several types of network routers that may be used in a given network. For instance, a packet switch such as Lucent""s PacketStar(trademark) (from Lucent Technologies, Inc. of Murray Hill, N.J.) IP Switch supports novel traffic scheduling and buffer management capabilities, including per-flow queuing with weighted fair queuing (WFQ) and longest-queue drop (LQD), which enable minimum bandwidth guarantees for VPNs while achieving a very high level of resource utilization. It is also known that existing legacy routers, on the other hand, do not support adequate flow isolation and their first-in-first-out (FIFO) scheduling, even when combined with the random early detection (RED) buffer management policy, results in little control over the bandwidth sharing among VPNs and throughput is mostly dictated by the dynamic properties of TCP (Transmission Control Protocol), which is the dominant transport protocol used in IP networks.
Accordingly, there is a need for a network design tool that permits users, i.e., network designers, to design IP networks having the same (homogeneous) or different (heterogeneous) types of routers which provide substantial performance guarantees for a variety of applications such as, for example, VPN. Specifically, there is a need for a design tool which: automatically computes worst-case and optimistic link capacity requirements based on a designer""s specifications; optimizes the network topology; and determines optimal router placement in the network.
The present invention provides methods and apparatus for designing IP networks with substantially improved performance as compared to existing IP networks such as, for example, those networks designed under best-effort criteria. Particularly, the invention includes methods and apparatus for: computing worst-case and optimistic link capacity requirements; optimizing network topology; and determining router placement within a network.
In a first aspect of the invention, methods and apparatus are provided for computing link capacity requirements of the links of the network. Particularly, upper and lower link capacity bounds are computable to provide the user of the design methodology with worst-case and optimistic results as a function of various design parameters. That is, given a network topology, specific IP demands and network delays, the design methodology of the invention permits a user to compute link capacity requirements for various network congestion scenarios, e.g., network-wide multiple bottleneck events, for each link of the given network. In this design methodology, the user may design the IP network, given a specific topology, without the need to know where specific bottlenecks are located within the specific network. Also, the link capacity computation methods and apparatus of the invention handle the case where there are one or more connections within a given demand.
In a second aspect of the invention, methods and apparatus are provided for optimizing the network topology associated with a network design. Particularly, an optimal network topology is formulated according to the invention which attempts to reduce overall network costs. In one embodiment, an iterative augmentation methodology is provided which attempts to reduce network costs by packing small -demands on the spare capacity of some existing links rather than introducing additional poorly utilized links into the network topology. In another embodiment, an iterative deloading methodology is provided which attempts to reduce network costs by removing identified links which are lightly loaded to form an optimal network topology.
In a third aspect of the invention, methods and apparatus are provided for determining the placement of WFQ/LQD routers in order to replace FIFO/RED routers in an existing network such that network cost savings are maximized. The methodology of the invention accomplishes such determination by employing a mixed integer programming model.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.